package LinkList;

import java.awt.*;
import java.util.Stack;

public class MySingleLinkList {
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;

    // 1、无头单向非循环链表实现
    public void CreatLinkList() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
    }

    //头插法
    public void addFirst(int data) {

        ListNode Node=new ListNode(data);
        Node.next=this.head;
        this.head=Node;
    }

    //尾插法
    public void addLast(int data) {

       ListNode Node=new ListNode(data);

       ListNode tail = head;
       if(tail==null){
           this.head=Node;
           return ;
       }

       while(tail.next!=null){
           tail=tail.next;
       }
       tail.next=Node;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        ListNode Node=new ListNode(data);
        if(index<0||index>size()){
            System.out.println("插入位置错误");
            return;
        }
        if(index==0){
            addFirst(data);
        }
        if(index==size()){
            addLast(data);
        }
        
        int count=index-1;
        ListNode cur=head;
        while(count>0){
            cur=cur.next;
            count--;
        }
        Node.next=cur.next;
        cur.next=Node;

    }

    public  ListNode findPrev(int key){
        if(head==null){
            return null;
        }
        ListNode cur=head;
        while (cur.next!= null) {
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
    //删除所有值为key的节点
    public void removeKey(int key) {
        ListNode prev = findPrev(key);
        if(head==null){
            throw new headnullException("链表为空异常");
        }
        if(head.val==key){
            head=head.next;
        } else {
            ListNode del=prev.next;
            prev.next=del.next;
        }

    }

 /*   public  void removeAllkey(int key){
        ListNode cur=this.head;
        for (ListNode i = cur; i !=null ; i=i.next) {
            if(i.val==key){
                removeKey(key);
            }
        }
    }*/
    public  void removeAllkey(int key){
        ListNode prev=head;
        ListNode cur=prev.next;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val==key){
            head=head.next;
        }
    }
    public void clear(){
        this.head=null;
    }
    public void display() {
        if(head==null){
            throw new headnullException("链表为空异常");
        }
        ListNode cur = head;
        System.out.print('[');
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println(']');
    }

    public void display(ListNode cur) {
        if(head==null){
            throw new headnullException("链表为空异常");
        }
        System.out.print('[');
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println(']');
    }
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }

    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.val==key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    public ListNode reverseList() {
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;

            cur.next=head;
            head=cur;

            cur=curNext;
        }
        return head;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead=null;
        ListNode A=list1.next;
        ListNode B=list2.next;

        if(list1.val>=list2.val){
            newHead=list2;
        }else{
            newHead=list1;
        }

        ListNode tmp=newHead;
        while(A!=null&B!=null){
            if(A.val<=B.val){
                tmp.next=A;
                tmp=tmp.next;
                A=A.next;
            }
            else{
                tmp.next=B;
                tmp=tmp.next;
                B=B.next;
            }
        }
        if(A!=null){
            tmp.next=A;
        }else{
            tmp.next=B;
        }
        return newHead;
    }
    public   ListNode partition( int x) {
        // write code here
        ListNode as=null;
        ListNode ae=null;
        ListNode bs=null;
        ListNode be=null;
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                if(as==null){
                    as=ae=cur;
                }
                else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            else{
                if(bs==null){
                    bs=be=cur;
                }
                else{
                    be.next=cur;
                    be=be.next;
                }
            }
            cur=cur.next;
        }
        if(as==null){
            return bs;
        }
        ae.next=bs;
        if(be.next!=null){
            be.next=null;
        }
        return as;
    }
    public boolean chkPalindrome() {
        // write code here
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
    public ListNode removeElements(int val) {
        while(head!=null&&head.val==val){
            head=head.next;
        }
        if(head==null){
            return null;
        }
        ListNode cur=head;
        while(cur!=null){
            if(cur.next!=null&&cur.next.val==val){
                ListNode del=cur.next;
                cur.next=del.next;
            }
            if(cur.next!=null&&cur.next.val!=val){
                cur=cur.next;
            }
        }
        return head;
    }
    public ListNode detectCycle() {
        if(head==null||head.next==null){
            return null;
        }
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=slow){
            if(fast==null||fast.next==null){
                return null;
            }
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode meeting=slow;
        while(head!=meeting){
            head=head.next;
            meeting=meeting.next;
        }
        return meeting;
    }
    public void reverse(){
        Stack<ListNode> stack= new Stack<>();
        ListNode cur=head;
        while(cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while(!stack.empty()){
            ListNode tmp=stack.peek();
            stack.pop();
            System.out.print(tmp.val+" ");
        }

    }
}